package com.example.demo.algorithm.heap;

/**
 * 堆存储结构
 *
 * @param <T>
 */
public class Heap<T extends Comparable<T>> {
    //堆中的元素个数
    private int N;
    //存储堆中的元素
    private T[] items;

    public Heap(int capacity) {
        this.items = (T[]) new Comparable[capacity++];
        this.N = 0;
    }

    /**
     * 判断i处的值是否小于J处的值
     *
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    /**
     * 交换i和j处的值
     */
    private void exch(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    /**
     * 往堆中插入一个元素
     */
    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    /**
     * 使用上浮的算法，使索引k处的元素能在堆中处于一个正确的位置
     *
     * @param k
     */
    private void swim(int k) {
        //通过循环，不断比较当前节点和其父节点，如果父节点的值比当前节点的值小，则交换位置
        while (k > 1) {
            if (less(k / 2, k)) {
                exch(k / 2, k);
            }
            //变换k的位置继续比较
            k = k / 2;
        }
    }

    /**
     * 删除对重最大的元素
     */
    public T delMax() {
        T max = items[1];
        //交换索引1处的元素和最大索引处的元素，最大索引处的的元素变为临时根节点
        exch(1, N);
        //最大索引处的元素删除
        items[N] = null;
        //元素个数减1
        N--;
        //使用下沉算法，让堆重新有序
        sink(1);
        return max;
    }

    /**
     * 使用下沉算法，使索引K处的元素在堆中处于一个正确的位置
     *
     * @param k
     */
    private void sink(int k) {
        while (2 * k <= N) {
            //找到k处的子节点的最大值
            int maxchileIndex = 2 * k;
            if (2 * k + 1 <= N) {
                if (less(2 * k, 2 * k + 1)) {
                    maxchileIndex = 2 * k + 1;
                }
            }
            //如果k的元素大于子节点的最大值，则结束循环
            if (!less(k, maxchileIndex)) {
                break;
            }
            //判断k处的元素和子节点的最大元素的大小，如果k的元素小于子节点的最大值，则交换位置
            exch(k, maxchileIndex);
            //变换k的值
            k = maxchileIndex;
        }


    }

}
